package com.dmall.play.interview.chapter08;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Leetcode77V2 {

    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || k > n) {
            return ans;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        findCombine(n, k, 1, stack);
        return ans;
    }

    private void findCombine(int n, int k, int index, Deque<Integer> stack) {
        if (stack.size() == k) {
            ans.add(new ArrayList<>(stack));
            return;
        }
        for (int i = index; i <= n - (k - stack.size()) + 1; i++) {
            stack.addLast(i);
            findCombine(n, k, i + 1, stack);
            stack.removeLast();
        }
    }

    public static void main(String[] args) {
        Leetcode77V2 leetcode = new Leetcode77V2();
        System.out.println(leetcode.combine(4, 2));
    }
}
